#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
const int inf=0x7fffffff;


int main(){
	int n;
	cin>>n;
	int a[n],w[n];
	int dp[n][n];
	for(int i=0;i<n;i++){
		cin>>a[i];
		dp[i][i] = 0;
		w[i] = i==0?a[i]:w[i-1]+a[i];
	}
	for(int len=2;len<=n;len++){
		for(int i=0;i<=n-len;i++){
			dp[i][i+len-1] = inf;
			for(int k=i;k<i+len-1;k++){
				dp[i][i+len-1] = min(dp[i][i+len-1],dp[i][k]+dp[k+1][i+len-1]);
			}
			dp[i][i+len-1] += w[i+len-1]-(i==0?0:w[i-1]);
		}
	}
	cout<<dp[0][n-1];
//	for(int i=0;i<n;i++){
//		for(int j=0;j<n;j++)
//			cout<<dp[i][j]<<" ";
//		cout<<endl;
//	}
//	for(int i=0;i<n;i++)
//		cout<<w[i]<<" ";
	return 0;
}
